package edu.iastate.cs228.hw4;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Template for Project 4, non-recursive merge sort.
 * 
 * @author Devon Eilers
 */
public class NonRecursiveMergeSort
{

  /**
   * Generic version of merge sort.  The type T is arbitrary, but the
   * caller must supply a comparator.  The algorithm must be implemented
   * non-recursively and must run in O(n log n) time.
   */
  public static <T> void mergeSort(T[] arr, Comparator<? super T> comp)
  {
	  int start = 0;
	  int end = arr.length-1;
	  Deque<StackItem> sortStack = new LinkedList<StackItem>();
	  sortStack.push(new StackItem(start,end, false));
	  StackItem cur;
	  while (!sortStack.isEmpty())
	  {
		  
		  cur = sortStack.poll();
		  if (cur.sorted) // hits element size of 1 or sorted subarrays
		  {
			  mergeWComp(arr, comp, cur.first, cur.last);
		  }
		  else
		  {
			  if (cur.first < cur.last)
			  {
				  int mid = ((cur.first+cur.last)/2);
				  sortStack.push(new StackItem(cur.first, cur.last, true));
				  sortStack.push(new StackItem(mid+1, cur.last, false)); // splits the current subarray into two parts to merge
				  sortStack.push(new StackItem(cur.first, mid, false));
			  }
		  }
	  }
	  
  }

  public static void main(String[] args) 
  {
	  Integer[] arr = {8,8,8,1};
	  mergeSort(arr);
	  
	  for (Integer z : arr) System.out.print(z + " ");
  }
  
  /**
   * Another generic version of merge sort.  This one imposes bounds on
   * T to guarantee that we can call the compareTo() method on objects of
   * type T.  The algorithm must be implemented non-recursively and must 
   * run in O(n log n) time.
   */
  public static <T extends Comparable<? super T>> void mergeSort(T[] arr)
  {
	  int start = 0;
	  int end = arr.length-1;
	  Deque<StackItem> sortStack = new LinkedList<StackItem>();
	  sortStack.push(new StackItem(start,end, false));
	  StackItem cur;
	  while (!sortStack.isEmpty())
	  {
		  
		  cur = sortStack.poll();
		  if (cur.sorted) // hits element size of 1 or sorted subarrays
		  {
			  merge(arr, cur.first, cur.last);
		  }
		  else
		  {
			  if (cur.first < cur.last)
			  {
				  int mid = ((cur.first+cur.last)/2);
				  sortStack.push(new StackItem(cur.first, cur.last, true));
				  sortStack.push(new StackItem(mid+1, cur.last, false)); // splits the current subarray into two parts to merge
				  sortStack.push(new StackItem(cur.first, mid, false));
			  }
		  }
	  }
  }
  
  /**
   * Merge portion of the merge sort algorithm
   * 
   * @param arr
   * 	- the array to merge
   * @param low
   * 	- the lower bound of the portion to be merged
   * @param high
   * 	- the upper bound of the portion to be merged
   */
  private static <T extends Comparable<? super T>> void merge(T[] arr, int low, int high)
  {
	  T[] merged = (T[]) new Comparable[arr.length];
	  
	  for (int i = low; i <= high; i++) merged[i] = arr[i];
	  
	  int i = low;
	  int mid = low + (high-low) / 2;
	  int j = mid+1;
	  int k = low;
	  
	  while (i <= mid && j <= high)
	  {
		  if (merged[i].compareTo(merged[j]) <= 0)
		  {
			  arr[k++] = merged[i++];
		  }
		  else
		  {
			  arr[k++] = merged[j++];
		  }
	  }
	  
	  while (i <= mid)
	  {
		  arr[k++] = merged[i++];
	  }
	  while (j <= high)
	  {
		  arr[k++] = merged[j++];
	  }

  }

/**
 * Merge portion of the merge sort algorithm with custom comparator
 * 
 * @param arr
 * 	- the array to merge
 * @param low
 * 	- the lower bound of the portion to be merged
 * @param high
 * 	- the upper bound of the portion to be merged
 */
private static <T> void mergeWComp (T[] arr, Comparator<? super T> comp, int low, int high)
{
	  T[] merged = (T[]) new Comparable[arr.length];
	  
	  for (int i = low; i <= high; i++) merged[i] = arr[i];
	  
	  int i = low;
	  int mid = low + (high-low) / 2;
	  int j = mid+1;
	  int k = low;
	  
	  while (i <= mid && j <= high)
	  {
		  if (comp.compare(merged[i], merged[j]) <= 0)
		  {
			  arr[k++] = merged[i++];
		  }
		  else
		  {
			  arr[k++] = merged[j++];
		  }
	  }
	  
	  while (i <= mid)
	  {
		  arr[k++] = merged[i++];
	  }
	  while (j <= high)
	  {
		  arr[k++] = merged[j++];
	  }	
}
  


}

